/*
leetcode 36: 有效的数独
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
 

注意：

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 '.' 表示。
 

示例 1：


输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true
示例 2：

输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
 

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 '.'
*/

#include <vector>
#include <unordered_set>
#include <iostream>
using namespace std;

bool isValidSudoku(vector<vector<char>>& board) {
    vector<unordered_set<char>> rows(9); // 存储每一行的数字
    vector<unordered_set<char>> cols(9); // 存储每一列的数字
    vector<unordered_set<char>> boxes(9); // 存储每个 3x3 子区域的数字

    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {

            char num = board[i][j];
            if (num == '.') continue; //如果当前格子是 '.'（空格），直接跳过。

            int boxIndex = (i / 3) * 3 + j / 3; // 计算子区域索引，通过该公式计算当前格子属于哪个子区域。

            // 检查行、列和子区域中是否已经存在该数字
            if (rows[i].count(num) || cols[j].count(num) || boxes[boxIndex].count(num)) {
                return false;
            }

            // 将数字添加到对应的集合中
            //rows[i]: 记录数字在第 i 行中出现。
            // cols[j]: 记录数字在第 j 列中出现。
            //boxes[boxIndex]: 记录数字在当前子区域中出现。
            rows[i].insert(num);
            cols[j].insert(num);
            boxes[boxIndex].insert(num);
        }
    }
    return true;
}

int main() {
    vector<vector<char>> board = {
        {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
        {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
        {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
        {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
        {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
        {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
        {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
        {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
        {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
    };

    cout << (isValidSudoku(board) ? "True" : "False") << endl;
    return 0;
}

/*
 遍历每个格子
按照 for (i, j) 遍历 9×9 的棋盘。

第一步：board[0][0]
当前格子：'5'，属于 第 0 行，第 0 列，左上角子区域。
检查：
rows[0]：空集合，数字 '5' 不存在。
cols[0]：空集合，数字 '5' 不存在。
boxes[0]：空集合，数字 '5' 不存在。
动作：将 '5' 插入：
rows[0] → { '5' }
cols[0] → { '5' }
boxes[0] → { '5' }

第二步：board[0][1]
当前格子：'3'，属于 第 0 行，第 1 列，左上角子区域。
检查：
rows[0]：{ '5' }，数字 '3' 不存在。
cols[1]：空集合，数字 '3' 不存在。
boxes[0]：{ '5' }，数字 '3' 不存在。
动作：将 '3' 插入：
rows[0] → { '5', '3' }
cols[1] → { '3' }
boxes[0] → { '5', '3' }

第三步：board[0][2]
当前格子：'.'，跳过。

第四步：board[0][4]
当前格子：'7'，属于 第 0 行，第 4 列，中间子区域。
检查：
rows[0]：{ '5', '3' }，数字 '7' 不存在。
cols[4]：空集合，数字 '7' 不存在。
boxes[1]：空集合，数字 '7' 不存在。
动作：将 '7' 插入：
rows[0] → { '5', '3', '7' }
cols[4] → { '7' }
boxes[1] → { '7' }

第五步：board[1][0]
当前格子：'6'，属于 第 1 行，第 0 列，左上角子区域。
检查：
rows[1]：空集合，数字 '6' 不存在。
cols[0]：{ '5' }，数字 '6' 不存在。
boxes[0]：{ '5', '3' }，数字 '6' 不存在。
动作：将 '6' 插入：
rows[1] → { '6' }
cols[0] → { '5', '6' }
boxes[0] → { '5', '3', '6' }

其余步骤
程序继续按顺序遍历，重复检查和插入：

遇到 '.' 跳过。
若数字未重复，插入到对应的 rows[i]、cols[j] 和 boxes[boxIndex]。
 */